package com.cheung.leetcode.normal;

import java.util.Arrays;

public class LC34 {

    public static int[] searchRange(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (target > nums[mid]) {
                low = mid + 1;
            }

            if (target < nums[mid]) {
                high = mid - 1;
            }

            if (target == nums[mid]) {
                int left = mid;
                int right = mid;

                while (left-1 >= 0 && nums[left-1] == nums[mid]) {
                    left--;
                }

                while (right+1 <= nums.length - 1 && nums[right+1] == nums[mid]) {
                    right++;
                }

                return new int[]{left, right};

            }
        }

        return new int[]{-1, -1};
    }


    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        System.out.println(Arrays.toString(searchRange(nums, 6)));
        System.out.println(Arrays.toString(searchRange(nums, 8)));
        System.out.println(Arrays.toString(searchRange(new int[]{1}, 1)));
    }
}
